package puzzle.projecteuler.p100;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.net.URL;
import java.net.URLDecoder;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import astudy.util.Combination;
import astudy.util.Permutation;

public class Problem098C {

	/**
	 * @param args
	 */
	public static void main(String[] args) throws IOException {
		
		long s = System.currentTimeMillis();
		String[] strs = readData();
		Map<String, List<String>> map = new HashMap<String, List<String>>();
		//获得所有字母相同的单词组
		for (String str: strs) {
			str = str.toUpperCase();
			char[] cs = str.toCharArray();
			Arrays.sort(cs);
			String key = new String(cs);
			if (map.get(key) == null) {
				map.put(key, new ArrayList<String>());
			}
			map.get(key).add(str);
		}
		//计算单词可能的所有数字置换，并计算最大的置换
		long M = 0;
		for (String key: map.keySet()) {
			if (map.get(key).size() > 1) {
				List<String> tmp = map.get(key);
				List<Map<Character, Integer>> substitutions = getAllSubstitutions(tmp);
				System.out.println(tmp);
				if (substitutions.size() > 0) {
					System.out.println(substitutions);
				}
				for (String t: tmp) {
					for (Map<Character, Integer> substitution: substitutions) {
						String u = t;
						for (Character c: substitution.keySet()) {
							u = u.replaceAll(c.toString(), String.valueOf(substitution.get(c)));
						}
						Long l = Long.valueOf(u);
						if (l > M) {
							M = l;
						}
					}
				}
			}
		}
		System.out.println(M);
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
	
	public static List<Map<Character, Integer>> getAllSubstitutions(List<String> strs) {
		
		List<Map<Character, Integer>> r = new ArrayList<Map<Character, Integer>>();
		char[] tmp = strs.get(0).toUpperCase().toCharArray();
		Set<Character> set = new HashSet<Character>();
		for (char c: tmp) set.add(c);
		if (set.size() > 10) {
			
		} else {
			Character[] cs = set.toArray(new Character[set.size()]);
			int[] c = new int[cs.length];
			for (int i = 0; i < c.length; i ++) {
				c[i] = i;
			}
			while (c != null) {
				int[] t = new int[c.length];
				System.arraycopy(c, 0, t, 0, t.length);
				while (t != null) {
					if (check(strs, cs, t)) {
						Map<Character, Integer> map = new HashMap<Character, Integer>();
						for (int i = 0; i < cs.length; i ++) {
							map.put(cs[i], t[i]);
						}
						r.add(map);
					}
					t = Permutation.next(t);
				}
				c = Combination.next(10, c);
			}
		}
		return r;
	}

	private static boolean check(List<String> strs, Character[] cs, int[] c) {
		
		for (String str: strs) {
			String tmp = str;
			for (int i = 0; i < cs.length; i ++) {
				tmp = tmp.replaceAll(cs[i].toString(), String.valueOf(c[i]));
			}
			if (tmp.charAt(0) == '0') {
				return false;
			} else {
				Long num = Long.valueOf(tmp);
				Long t = (long)Math.sqrt(num);
				if (t*t != num) return false;
			}
		}
		return true;
	}

	public static String[] readData() throws IOException {

		URL url = Problem098C.class.getResource("Problem098.txt");
		File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));

		BufferedReader br = new BufferedReader(new FileReader(file));
		String line = br.readLine();
		br.close();
		return line.replace("\"", "").split(",");
	}
}
